435. 无重叠区间

Similar Question

452. 用最少数量的箭引爆气球

Solution Tips

方案一: 排序 + 贪心

var eraseOverlapIntervals = function(intervals) {
    // 只要有重合就一定要删除呀, 但是会不会有更好删除选项呢?
    // 参考 452 只要右边大于 next 左边 就需要删除
    // 只关心右边, 所以直接按照右边排序即可
    intervals.sort((a, b) => a[1] - b[1]);

    // 做 leetcode 经常没有注意入参的范围, 但是其实还是需要注意一样的
    // 错了是有惩罚的
    let safeRight = Number.MIN_SAFE_INTEGER;
    let res = 0;
    for (let i = 0; i < intervals.length; i++) {
        const [l ,r] = intervals[i];
        if (safeRight > l) {
            // 需要删除
            res++;
        }
        else {
            // 无需删除, 更新 safeRight
            safeRight = r;
        }
    }

    return res;
};
console.log(eraseOverlapIntervals([[1,2],[2,3],[3,4],[-100,-2],[5,7]]))

方案二: Dp